KURZUS: Alkalmazott operációkutatás

MODUL: II. modul: Egészértékű programozási feladat fogalma és grafikus megoldása. Néhány nevezetes egészértékű modell

Modulzáró feladatok

|  | 1. feladat
| Írja fel a "hátizsák probléma" matematikai modelljét! A hátizsák térfogatát jelöljük V-vel, a hátizsákban elviendő tárgy térfogatát v j -vel, a tárgy használati értékét h j -vel, a döntési változókat x j -vel, a tárgyak száma n db.
| Írja ide a feltételeket:
| a) A változókra vonatkozó feltételek: x j = vagy , ahol j = , ..., . 1 pont
| b) Feltétel(ek):
Együtthatók | Reláció | Jobb oldal
| x 1 + |  | x 2 +...+ |  | x n |  |
2 pont
| c) Célfüggvény (Indexek helyett írjon csak számokat! Pl. x1, h1 stb.) x 1 + x 2 +...+ x n → 2 pont
| 2. feladat
| Többcélú lineáris programozási modellt akarjuk megoldani, de csak olyan számítógépes megoldási program áll rendelkezésre (Pl. Solver), amely csak egy célfüggvényt tud kezelni. Hogyan járjunk el?
| x 1 , x 2 ≥ 0 2 x 1 +3 x 2 ≤ 80 − x 1 +2 x 2 ≤ 50 z 1 =3 x 1 +7 x 2 → max⁡ z 2 =8 x 1 +5 x 2 → max⁡
| Készítsen a két célfüggvényből egyet úgy, hogy
| a) az első célfüggvény súlya 70%, a másodiké 30% legyen. Írja ide a célfüggvény együtthatóit: x 1 + x 2 → 1 pont
| b) a korlátok módszerét használja (11 legyen a 2. célfüggvény alsó korlátja). Akkor a modell (a kisebb-egyenlő és nagyobb egyenlő megadásához használja a <= és >= jeleket!):
| x 1 | x 2 | reláció | jobb oldal
z |  |  | → |
2 pont
| c) a legkisebb célfüggvény értékének maximalizálása elvet használja (Az eredeti adatokkal dolgozzon!). A modell ebben az esetben:
| x 1 | x 2 | y | reláció | jobb oldal
−z |  |  |  | → |
3 pont
| 3. feladat
| Tegyük fel, hogy három feladóhelyen 30, 40 és 50 tonna áru van. Négy megrendelőhöz kell szállítani 20, 15, 60 és 55 tonnát. A 2. feladótól a 3. megrendelőnek technikai okok miatt nem lehet szállítani. A 1. megrendelő a sógorom, ezért az ő igényét mindenképpen ki kell elégíteni! A szállítási költségek mátrixa a következő (100 Ft/tonna):
| [ 8 2 4 1 7 7 1 4 3 2 1 2 5 1 5 2 6 ]
| a) Írja fel a feladatokra vonatkozó feltételek együtthat mátrixát, relációjeleket és a jobb oldalt (a kisebb-egyenlő és nagyobb egyenlő megadásához használja a <= és >= jeleket, ha szükséges!):
| Együtthatók | Relációk | Jobb oldal
1. feladó |  | x11 |  | x12 |  | x13 |  | x14 |  |
2. feladó |  | x21 |  | x22 |  | x23 |  | x24 |  |
3. feladó |  | x31 |  | x32 |  | x33 |  | x34 |  |
3 pont
| b) Írja fel az igénylőkre vonatkozó feltételrendszer együttható mátrixát, a relációjeleket és a jobb oldalt (a kisebb-egyenlő és nagyobb egyenlő megadásához használja a <= és >= jeleket!):
| Együttható mátrix | Reláció | Jobb oldal
1. megrendelő |  |  |  |  |
2. megrendelő |  |  |  |  |
3. megrendelő |  |  |  |  |
4. megrendelő |  |  |  |  |
4 pont
| c) Mit fejez ki a modell változója?
| A modell változója xij azt jelenti, hogy...
| az i-edik feladótól a j-edik megrendelőnek xij tonnát szállítunk.
| az i-edik feladótól a j-edik megrendelőnek xij Ft költséggel szállítunk egy tonna árút.
| az i-edik feladótól a j-edik megrendelőnek szállítunk árút, azaz értéke 0 vagy 1 lehet.
1 pont
| 4. feladat
| Oldja meg a Solver programmal a következő hiperbolikus programozási feladatot!
| x 1 , x 2 , x 3 ≥ 0 x 1 + x 3 = 50 − x 1 + x 2 + x 3 ≥ 100 x 3 ≥ 10 g( x )= 8 x 1 + x 2 +2 x 3 +100 2 x 1 +2 x 2 +3 x 3 −130 → max⁡
| a) Adja meg x1 értékét: x 1 = 2 pont
| b) Adja meg x2 értékét: x 2 = 2 pont
| c) Adja meg x3 értékét: x 3 = 2 pont
| d) Adja meg Zopt értékét: z o p t = 4 pont
| 5. feladat
| Oldja meg a következő hozzárendelési feladatot a szétválasztás és korlátozás módszerével: Egy üzemben 4 munkásnak kell kiosztani 3 feladatot úgy, hogy az összköltség a lehető legkisebb legyen!
| A költségmátrix:
| [ 3 7 10 9 1 8 4 12 8 11 7 4 ]
| Feltételek:
| Minden munkás minden feladatot képes elvégezni A 2. munkás a 2. feladatot most valamilyen ok miatt nem kaphatja meg A 3. munkás a sógorom, ezért ő mindenképpen kapjon munkát.
| Vegyen elő egy négyzetrácsos lapot és oldja meg a feladatot a szétválasztás és korlátozás módszerével!
| a) Írja ide a feladat kiegészített költségmátrixát:
2 pont
| b) Írja ide a redukált mátrixot (oszlop redukcióval kezdje)
2 pont
| c) Adja meg a redukció értékét, a költség alsó korlátját! A redukció értéke: 1 pont
| d) Adja meg az optimális megoldást: egészítse ki az elkezdett mondatokat! Első munkás kapja a(z) . munkát. A második munkás a(z) . munkát. A harmadik munkás a(z) . munkát. A negyedik munkás a(z) . munkát. 4 pont
| e) Adja meg a legkisebb költség értékét! A legkisebb költség értéke: 1 pont